The invention relates to methods and systems for structuring data, and more particularly to a method and system for accessing and storing data of a centralized linked list data structure in a computer system.
There are many different forms of electronic data structures and each different data structure can have a myriad of implementations. One such data structure is in the form of a xe2x80x9clistxe2x80x9dxe2x80x94i.e., a grouping of ordered items that can be sequenced. A list that contains respective items and information to reach a prior or a subsequent item is referred to as a xe2x80x9clinked list.xe2x80x9d With a xe2x80x9csingle linked list,xe2x80x9d each item only has a reference to the next list item. More sophisticated forms of electronic data structures are configured as a xe2x80x9cdouble linked listxe2x80x9d or xe2x80x9ccircular linked listxe2x80x9d which consist of a chain of records (called nodes) in which the list is implemented by having a link to an adjacent data item.
FIG. 1 illustrates a double linked list. Each node 1, 2, 3 of the linked list includes content 10, 14, 18, and forward/backward pointers 12, 16 to the next node in the linked list. The last node 3 in the double linked list has a null pointer 20, i.e., it does not point to another node. A circular linked list is similar to the double linked list illustrated in FIG. 1, but differs from the double linked list in that the last node of the linked list has a pointer back to the first node.
The nodes of a linked list are connected like links of a chain; in the case of a circular linked list, the first pointer 12 is connected to last pointer 20 of the list illustrated in FIG. 1. Unlike the double linked list, in the case of a circular linked list, last pointer 20 points to the first node of the list. A linked list has a head pointer 8 for accessing that specific list. Head pointer 8 has linear links to subsequent nodes 2, 3, 4. The entire list is referenced from head 8.
Prior art linked list data structures, such as a double linked list and a circular linked list, operate systematically in the following manner. The beginning of the linked list is stored at head 8, which points to the first node 1. The first node 1 then points to the second node 2, and so forth, until reaching the last node 3. Though the linked list shown in FIG. 1 illustrates a list with head 8 and three nodes, it will be appreciated that additional nodes may be placed between head 8 and last node 3. This means that any node 1, 2, 3 can be accessed with a start at head 8 and follows the next pointer 12 to get to the queried pointer (12 or 16). While this may be systematic, it also means that there is a linear cost of operationxe2x80x94i.e., data is searched one item by item, starting from the beginning of the list and moving toward the end of the list. Thus, operations that rely on data towards the front of a linked list are fast, while operations that rely on data toward the end of a linked list will be slower.
In addition, prior art linked lists are typically implemented in databases, and are therefore stored in permanent memory devices. While such permanent memory devices, such as disk drives and tape drives, can provide large amounts of memory storage, they have proved to be slow in storing and accessing data when large linked lists, or large sets of linked lists, are used. In addition, such linked lists are structured with one or more layers of lists requiring large amounts of sequential data processing time.
An example of a prior art linked list data structures is disclosed in U.S. Pat. No. 6,249,788, entitled xe2x80x9cStructure for a Database.xe2x80x9d The data structure described therein stores different data within an associated linked list in order to reduce the amount of sequential information searched. The described link list relates to a hierarchy of nodes consisting of a tree-structure which includes a root node, intermediate nodes and leaf nodes. An element of the root node establishes a link to a first intermediate node and then to subsequent intermediate node(s), which in turn link to a plurality of link nodes. Thus, such associated linked lists include sequential layers of data storage and therefore often require a great deal of processing time to search data of the linked list.
Prior art linked list data structures, such as that disclosed in U.S. Patent Application Publication No. 2002/0004793, entitled xe2x80x9cMethod and Apparatus for Organizing Data by Overlaying a Searchable Database with a Directory Tree Structure,xe2x80x9d assign multiple links between nodes. Pointers are used to link related data items. However, searching related data items still follows a branched path across several child nodes before returning to a parent node. Each step in the process requires added processing time. Moreover, when pointer bugs occur, it is often difficult to identify where the crash has occurred. Each linked must be sequentially tested until the bug is found. Thus, the debugging process can be both time and labor intensive.
Accordingly, there remains an unmet need in data structures for a fast, efficient and reliable data structure which does not suffer from the drawbacks described above.
In accordance with an embodiment of the invention, a central linked list comprises a parent node which is situated at the center of a plurality of child nodes. Each child node has two double linked list pointers. One pointer points to the next child node, and the other pointer points to the parent node. Thus, matched data obtained at several child nodes moves back to the parent simultaneously.
In accordance with another embodiment of the invention, the parent node contains the memory address and name of central linked list, a description of central linked list, and a description of the relationship between other parent nodes, as well as the relationship between each child node to its specific parent node. Each child node contains a node address, an attribute comprised of some or all of the stored data field and a link to the full data content that may reside on a file or in a database.
In accordance with yet another embodiment of the invention, memory storage of the structure information is stored in system memory, such as, random access memory (RAM). Thus, searching and comparison operations may be accomplished without the need to access data stored by a hard disk.